package niuke.week3;

import java.util.Scanner;

/**
 给定一个字符串str，如果可以在str的任意位置添加字符，请返回在添加字符最少的情况下，让str整体都是回文字符串的一种结果。


 输出一行，代表返回的字符串。
 */
public class AddCharGetHuiWenChuanAber {

    static  Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        String next = sc.next();
        char[] chars = next.toCharArray();
        System.out.println(addChar(chars));
    }

    public static String addChar(char [] chars){
        int n = chars.length;
        int [][]dp = new int[n][n];//dp_i,j  char[i...j]添加几个构成回文串

        for (int j = 1; j < chars.length; j++) {
            dp[j - 1][j] = chars[j - 1] == chars[j] ? 0 : 1;//两个字符的时候
            for (int i = j - 2; i > -1; i--) {
                if (chars[i] == chars[j]) {
                    dp[i][j] = dp[i + 1][j - 1];//两字符相等
                } else {///////////////   a_i         a_j
                    dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1;
                }
            }
        }

        int addNumber = dp[0][chars.length - 1];
        char[] res = new char[n + addNumber];
        int i = 0;
        int j = chars.length - 1;
        int resl = 0;
        int resr = res.length - 1;
        while (i <= j) {
            if (chars[i] == chars[j]) {//字符相等 a........a
                res[resl++] = chars[i++];
                res[resr--] = chars[j--];
            } else if (dp[i][j - 1] < dp[i + 1][j]) { //  [a_i ... a_j-1] a_j
                res[resl++] = chars[j];
                res[resr--] = chars[j--];
            } else { //  a_i[a_i+1 ... a_j]
                res[resl++] = chars[i];
                res[resr--] = chars[i++];
            }
        }
        return  String.valueOf(res);
    }
}